import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-05-14
 * Time: 11:00
 */
public class Test2 {
    public static List<String> topKFrequent(String[] words, int k) {
        //1. 每个单词数显的次数
        Map<String, Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        //2. 创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry:
                map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(entry.getValue().compareTo(top.getValue()) == 0) {
                    //频率一样，判断字典序
                    if(entry.getKey().compareTo(top.getKey()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            list.add(s);
        }
        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {
        String[] strings = {"a", "b", "c", "c"};
        List<String> list = topKFrequent(strings, 3);
    }
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();
        String string2 = in.nextLine();
        Set<Character> set = new HashSet<>();
        for(char c : string2.toUpperCase().toCharArray()) {
            set.add(c);
        }
        Set<Character> set2 = new HashSet<>();
        for(char c : string.toUpperCase().toCharArray()) {
            if(!set.contains(c) && !set2.contains(c)) {
                System.out.print(c);
                set2.add(c);
            }
        }

    }
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
//        for (int i = 0; i < jewels.length(); i++) {
//            set.add(jewels.charAt(i));
//        }
        for (char c:
                jewels.toCharArray()) {
            set.add(c);
        }
        int count = 0;
//        for (int i = 0; i < stones.length(); i++) {
//            if (set.contains(stones.charAt(i))) {
//                count++;
//            }
//        }
        for (char c:
                stones.toCharArray()) {
            if(set.contains(c)) {
                count++;
            }
        }
        return count;
    }
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
}
